// m

// 给定一个无重复元素的正整数数组candidates和一个正整数target，找出candidates中所有可以使数字和为目标target的唯一组合
// 数组candidates中的数字可以无限重复选取，  1 <= candidates <= 200

// 解题思路，回溯算法
// 建立两个数组res，path，res用于存放所有满足提议的组合，path用于存放满足题意的一个组合
// 定义回溯方法，start_index = 1开始进行回溯
// 1. 如果sum > target, 则直接返回
// 2. 如果sum == target, 则将path中的元素加入到res数组中
// 3. 然后对[start_index, n]范围内的数进行遍历取值
//      1. 如果sum+candidates[i] > target, 可以直接跳出循环
//      2. 将和累加，即sum += candidates[i],然后将当前元素加入path数组
//      3. 递归遍历[start_index, n]上的数
//      4. 和回退，即sum -= candidates[i],然后将遍历的i元素进行回退
// 最终返回res数组

function combinationSum(candidates, target) {
    let res = []
    let path = []
    function backtrack(candidates, target, sum, start_index) {
        if (sum > target) {
            return
        }
        if (sum === target) {
            res.push([...path])
            return
        }
        for (let i = start_index; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break
            }
            sum += candidates[i]
            path.push(candidates[i])
            backtrack(candidates, target, sum, i)
            sum -= candidates[i]
            path.pop()
        }
    }

    candidates.sort((x, y) => x - y)
    backtrack(candidates, target, 0, 0)
    return res
}

let candidates = [2, 3, 5], target = 8
console.log(combinationSum(candidates, target))


